package advanced.sorting;

public class InsertionSort {
	
	//insertion sort using two for loops
    public static void insertionSort1(int [] num)
    {
    	int nextValue=0;//the next value to insert
    	int count=0;
    	//looping through the unsorted list, starting from position 1 because position 0 is considered sorted
    	for(int i=1; i<num.length; i++)
    	{
    		nextValue=num[i];//sets the next value to be the value of current index, and this value will be inserted into the correct position after the inner loop ends
    		int j;
    		for(j=i-1; j>=0; j--)
    		{
    			//if the value of the element is greater than the next value, move the position up by 1
    			//else stop the loop, and insert the next value
    			if(num[j]>nextValue)
    			{
    				num[j+1]=num[j];
    			}
    			else
    			{
    				break;
    			}
    			count++;
    		}
    		num[j+1]=nextValue;//insert the next value into the correct position, j+1 because the last operation in the for loop decremented the j by 1
    		System.out.print("During sorting: ");printArr(num);
    	}
    	System.out.println("Total number of loops: "+count);
    }
    
    //insertion sort using an outer for loop and an inner while loop
    public static void insertionSort2(int[] num)
    {
    	int nextValue=0;//the next value to insert
    	int j=0;
    	int count=0;
    	for(int i=1; i<num.length; i++)
    	{
    		nextValue=num[i];//sets the next value to be the value of current index, and this value will be inserted into the correct position after the inner loop ends
    		j=i-1;
    		//while the value of the element is greater than the next value and j is greater than or equal than 0, 
    		//move the position up by 1
    		while(j>=0 && num[j]>nextValue)
    		{
    			num[j+1]=num[j];
    			j--;
    			count++;
    		}
    		num[j+1]=nextValue;//insert the next value into the correct position, j+1 because the last operation in the while loop decremented the j by 1
    		System.out.print("During sorting: ");printArr(num);
    	}
    	System.out.println("Total number of loop: "+count);
    }
    
	public static void printArr(int[] arr)
	{
		for(int i=0; i<arr.length; i++)
		{
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
	public static void main(String []args) { 
		int [] intArr={3,4,64,3,1,13,8,22};
		System.out.print("Before: ");printArr(intArr);
		InsertionSort.insertionSort1(intArr);
		System.out.print("After: ");printArr(intArr);
	  }

}
